/**
 * 求长度为N的且所有长度为2的子串至少有一个1字符串 
 * 注意到N不是很大，因此首先写出所有的字符串
 * 然后在检查即可
 */
class Solution {
public:
    vector<string> validStrings(int n) {
        if(1 == n) return vector<string>{"0", "1"};

        vector<string> ans;
        for(int st=1;st<(1<<n);++st){
            string s(n, '0');
            for(int i=0;i<n;++i){
                if((1 << i) & st){
                    s[i] = '1';
                }
            }
            if(check(s)){
                ans.emplace_back(s);
            }
        }
        return ans;
    }
    
    bool check(const string & s){
        for(int i=1;i<s.length();++i){
            if('0' == s[i - 1] and '0' == s[i]) return false;
        }
        return true;
    }
};